package stack;

import java.util.LinkedList;

public class LongestValidParentheses32 {
    public int longestValidParentheses(String s) {
        int[] rest = new int[s.length()];
        for (int i = 0; i < rest.length; i++) {
            rest[i] = 0;
        }
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ')') {
                int m = i - 1;
                while (m > -1 && rest[m] == 1) {
                    m--;
                }
                if (m >= 0 && s.charAt(m) == '(') {
                    rest[i]=1;
                    rest[m]=1;
                }
            }
        }
        int max = 0;
        int count = 0;
        for (int i = 0; i < rest.length; i++) {
            if(rest[i]==1){
                count++;
            }else {
                max=max>count?max:count;
                count=0;
            }
        }
        return max>count?max:count;
    }


//    public int longestValidParentheses(String s) {
//        if (s == null || s.length() == 0) {
//            return 0;
//        }
//
//        LinkedList<Character> stack = new LinkedList<>();
//        int count = 0;
//        int max = 0;
//        for (int i = 0; i < s.length(); i++) {
//            char c = s.charAt(i);
//            if (c == ')' && stack.size() != 0) {
//                if (stack.getLast() == '(') {
//                    stack.pollLast();
//                    count++;
//                    max = max > count ? max : count;
//                    continue;
//                } else {
//                    count = 0;
//                }
//            }
//            stack.offerLast(c);
//        }
//
//        return max*2;
//    }
}
